{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Vertical Order Traversal of a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: verticalTraversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的垂序遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉树的根结点 <code>root</code> ，请你设计算法计算二叉树的<em> </em><strong>垂序遍历</strong> 序列。</p>\n",
    "\n",
    "<p>对位于 <code>(row, col)</code> 的每个结点而言，其左右子结点分别位于 <code>(row + 1, col - 1)</code> 和 <code>(row + 1, col + 1)</code> 。树的根结点位于 <code>(0, 0)</code> 。</p>\n",
    "\n",
    "<p>二叉树的 <strong>垂序遍历</strong> 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。</p>\n",
    "\n",
    "<p>返回二叉树的 <strong>垂序遍历</strong> 序列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/29/vtree1.jpg\" style=\"width: 431px; height: 304px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,9,20,null,null,15,7]\n",
    "<strong>输出：</strong>[[9],[3,15],[20],[7]]\n",
    "<strong>解释：</strong>\n",
    "列 -1 ：只有结点 9 在此列中。\n",
    "列  0 ：只有结点 3 和 15 在此列中，按从上到下顺序。\n",
    "列  1 ：只有结点 20 在此列中。\n",
    "列  2 ：只有结点 7 在此列中。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/29/vtree2.jpg\" style=\"width: 512px; height: 304px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,5,6,7]\n",
    "<strong>输出：</strong>[[4],[2],[1,5,6],[3],[7]]\n",
    "<strong>解释：</strong>\n",
    "列 -2 ：只有结点 4 在此列中。\n",
    "列 -1 ：只有结点 2 在此列中。\n",
    "列  0 ：结点 1 、5 和 6 都在此列中。\n",
    "          1 在上面，所以它出现在前面。\n",
    "          5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。\n",
    "列  1 ：只有结点 3 在此列中。\n",
    "列  2 ：只有结点 7 在此列中。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/29/vtree3.jpg\" style=\"width: 512px; height: 304px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,6,5,7]\n",
    "<strong>输出：</strong>[[4],[2],[1,5,6],[3],[7]]\n",
    "<strong>解释：</strong>\n",
    "这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。\n",
    "因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中结点数目总数在范围 <code>[1, 1000]</code> 内</li>\n",
    "\t<li><code>0 <= Node.val <= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [vertical-order-traversal-of-a-binary-tree](https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [vertical-order-traversal-of-a-binary-tree](https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,20,null,null,15,7]', '[1,2,3,4,5,6,7]', '[1,2,3,4,6,5,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        \n",
    "        idx_nodes = collections.defaultdict(list)\n",
    "        \n",
    "        q = deque([])\n",
    "        q.append((root, 0))\n",
    "        max_idx = min_idx = 0\n",
    "        while q:\n",
    "            level_size = len(q)\n",
    "            cur_idx_nodes = collections.defaultdict(list)\n",
    "            for _ in range(level_size):\n",
    "                cur, idx = q.popleft()\n",
    "                cur_idx_nodes[idx].append(cur.val)\n",
    "                max_idx = max(max_idx, idx)\n",
    "                min_idx = min(min_idx, idx)\n",
    "                if cur.left:\n",
    "                    q.append((cur.left, idx-1))\n",
    "                if cur.right:\n",
    "                    q.append((cur.right, idx+1))\n",
    "            for idx, lst in cur_idx_nodes.items():\n",
    "                idx_nodes[idx] += sorted(lst)\n",
    "        res = []\n",
    "        for idx in range(min_idx, max_idx+1):\n",
    "            res.append(idx_nodes[idx])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: 'TreeNode') -> 'List[List[int]]':\n",
    "        if not root:\n",
    "            return []\n",
    "        memo = {}\n",
    "        def dfs(root,memo,x,y):\n",
    "            if x in memo:\n",
    "                if y in memo[x]:\n",
    "                    memo[x][y].append(root.val)\n",
    "                else:\n",
    "                    memo[x][y] = [root.val]\n",
    "            else:\n",
    "                memo[x] = {}\n",
    "                memo[x][y] = [root.val]\n",
    "                \n",
    "            if not root.left and not root.right:\n",
    "                return\n",
    "            else:\n",
    "                if root.left:\n",
    "                    dfs(root.left,memo,x-1,y+1)\n",
    "                if root.right:\n",
    "                    dfs(root.right,memo,x+1,y+1)\n",
    "                    \n",
    "        dfs(root,memo,0,0)\n",
    "        res = []\n",
    "        while(len(memo) > 0):\n",
    "            x_dict = memo.pop(min(memo))\n",
    "            tmp = []\n",
    "            while(len(x_dict) > 0):\n",
    "                tmp = tmp + sorted(x_dict.pop(min(x_dict)))\n",
    "            res.append(tmp)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root, x, y):\n",
    "        if root is None:\n",
    "            return\n",
    "        \n",
    "        if x not in self.pool:\n",
    "            self.pool[x] = []\n",
    "        self.pool[x].append((y, self.cnt, root.val))\n",
    "        self.cnt += 1\n",
    "        \n",
    "        self.dfs(root.left, x - 1, y - 1)\n",
    "        self.dfs(root.right, x + 1, y - 1)\n",
    "    \n",
    "    def verticalTraversal(self, root: 'TreeNode') -> 'List[List[int]]':\n",
    "        self.pool = {}\n",
    "        self.cnt = 0\n",
    "        self.dfs(root, 0, 0)\n",
    "        \n",
    "        klist = sorted(list(self.pool.keys()))\n",
    "        ans = []\n",
    "        for k in klist:\n",
    "            cur = self.pool[k]\n",
    "            # print(k, cur)\n",
    "            cur.sort(key=lambda x: (-x[0], x[2]))\n",
    "            cur = [e[-1] for e in cur]\n",
    "            ans.append(cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: 'TreeNode') -> 'List[List[int]]':\n",
    "        dic = {}\n",
    "        self.dfstree(root, dic, 0, 0)\n",
    "        keys = sorted(dic)\n",
    "        ret = []\n",
    "        for key in keys:\n",
    "            roots = dic.get(key)\n",
    "            rootkeys = sorted(roots)\n",
    "            temp = []\n",
    "            for x in rootkeys:\n",
    "                temp.append(x[1])\n",
    "            ret.append(temp)\n",
    "        return ret\n",
    "        \n",
    "    def dfstree(self, root, dic, val, layer):\n",
    "        if(root is None):\n",
    "            return\n",
    "        print(str(root.val) + ' ' + str(val))\n",
    "        if dic.get(val) is None:\n",
    "            dic[val] = [[layer, root.val]]\n",
    "        else:\n",
    "            dic[val] += [[layer, root.val]]\n",
    "        self.dfstree(root.left, dic, val-1, layer+1)\n",
    "        self.dfstree(root.right, dic, val+1, layer+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "class Point:\n",
    "  def __init__(self,x:int,y:int,val:int):\n",
    "    self.x = x\n",
    "    self.y = y\n",
    "    self.val = val\n",
    "\n",
    "  def __str__(self):\n",
    "    return \"%d,%d=%d\" % (self.x,self.y,self.val)\n",
    "\n",
    "  def __repr__(self):\n",
    "    return str(self)\n",
    "\n",
    "class Solution:\n",
    "  def verticalTraversal(self, root: 'TreeNode') -> 'List[List[int]]':\n",
    "    if not root:\n",
    "      return []\n",
    "    points = []\n",
    "    root.point = Point(1000,1000,root.val)\n",
    "    nodes = [root]\n",
    "    while nodes:\n",
    "      node = nodes.pop()\n",
    "      point = node.point\n",
    "      points.append(point)\n",
    "      left = node.left\n",
    "      right = node.right\n",
    "      if left:\n",
    "        left.point = Point(point.x -1, point.y -1, left.val)\n",
    "        nodes.append(left)\n",
    "      if right:\n",
    "        right.point = Point(point.x +1, point.y -1, right.val)\n",
    "        nodes.append(right)\n",
    "    x_to_points = defaultdict(list)\n",
    "    for point in points:\n",
    "      x_to_points[point.x].append(point)\n",
    "    for _,points in x_to_points.items():\n",
    "      points.sort(key=lambda p:(-p.y,p.val))\n",
    "    results = []\n",
    "    xlist = sorted(x_to_points.keys())\n",
    "    for x in xlist:\n",
    "      points = x_to_points[x]\n",
    "      values = [p.val for p in points]\n",
    "      results.append(values)\n",
    "    return results\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:\n",
    "        stack = [(root,0,0)]\n",
    "        res = []\n",
    "        while stack:\n",
    "            node,x,y = stack.pop(0)\n",
    "            res.append((x,y,node.val))\n",
    "            if node.left:\n",
    "                stack.append((node.left,x-1,y-1))\n",
    "            if node.right:\n",
    "                stack.append((node.right,x+1,y-1))\n",
    "        res.sort(key=lambda x:(x[0],-x[1],x[2]))\n",
    "        #print(res)\n",
    "        result,prex = [],None\n",
    "        for x,y,val in res:\n",
    "            if x == prex:\n",
    "                result[-1].append(val)\n",
    "            else:\n",
    "                result.append([val])\n",
    "                prex = x\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution(object):\n",
    "    def verticalTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not root: return \n",
    "        \n",
    "        vals = []\n",
    "        def preOrder(root, x, y):\n",
    "            if not root: return\n",
    "            vals.append((x, y, root.val))            \n",
    "            preOrder(root.left, x-1, y + 1)\n",
    "            preOrder(root.right, x+1, y + 1)\n",
    "\n",
    "        preOrder(root, 0, 0)\n",
    "        res = []\n",
    "        lastx = -99999\n",
    "        for x, y, val in sorted(vals):\n",
    "            if x != lastx:\n",
    "                res.append([])\n",
    "                lastx = x\n",
    "            res[-1].append(val)\n",
    "\n",
    "\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef verticalTraversal(self,root):\n",
    "\t\tdef getDepth(root):\n",
    "\t\t\tif root:\n",
    "\t\t\t\treturn max(getDepth(root.left),getDepth(root.right))+1\n",
    "\t\t\treturn 0\n",
    "\t\tans=[[] for _ in range(2*getDepth(root)-1)]\n",
    "\t\tdef bfs(root,idx):\n",
    "\t\t\tnodes=[root]\n",
    "\t\t\tidxs=[idx]\n",
    "\t\t\twhile nodes:\n",
    "\t\t\t\tnew_n,new_i=[],[]\n",
    "\t\t\t\ttmp_dict=dict()\n",
    "\t\t\t\tfor n,i in zip(nodes,idxs):\n",
    "\t\t\t\t\ttmp_dict.setdefault(i,[]).append(n.val)\n",
    "\t\t\t\t\tif n.left:\n",
    "\t\t\t\t\t\tnew_n.append(n.left)\n",
    "\t\t\t\t\t\tnew_i.append(i-1)\n",
    "\t\t\t\t\tif n.right:\n",
    "\t\t\t\t\t\tnew_n.append(n.right)\n",
    "\t\t\t\t\t\tnew_i.append(i+1)\n",
    "\t\t\t\tnodes,idxs=new_n,new_i\n",
    "\t\t\t\tfor i,j in tmp_dict.items():\n",
    "\t\t\t\t\tans[i].extend(sorted(j))\n",
    "\t\tbfs(root,len(ans)//2)\n",
    "\t\treturn list(filter(bool,ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        # dic[x] = [val1, val2...]\n",
    "        dic = {}\n",
    "        temp_dic = {}\n",
    "        # node, x\n",
    "        nodelist = [(root, 0)]\n",
    "        next_nodelist = []\n",
    "        while(len(nodelist)>0):\n",
    "            next_nodelist.clear()\n",
    "            temp_dic.clear()\n",
    "            for node, x in nodelist:\n",
    "                if node.left:\n",
    "                    next_nodelist.append([node.left, x-1])\n",
    "                if node.right:\n",
    "                    next_nodelist.append([node.right, x+1])\n",
    "                if x not in temp_dic:\n",
    "                    temp_dic[x] = []\n",
    "                temp_dic[x].append(node.val)\n",
    "            nodelist = next_nodelist.copy()\n",
    "            for x, v in temp_dic.items():\n",
    "                if x not in dic:\n",
    "                    dic[x] = []\n",
    "                dic[x] += sorted(v)\n",
    "        result = []\n",
    "        sort_x = sorted(dic.keys())\n",
    "        for x in sort_x:\n",
    "            result.append(dic[x])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:\n",
    "        self.res = {}\n",
    "\n",
    "        def bfs(root):\n",
    "            q = [(root,(0,0))]\n",
    "            \n",
    "            while q:\n",
    "                cur_q = q\n",
    "                q = []\n",
    "                lx = ly = lval = -1\n",
    "                for node,(x,y) in cur_q:\n",
    "                    if x not in self.res.keys():\n",
    "                        self.res[x] = {}\n",
    "                    if y not in self.res[x].keys():\n",
    "                        self.res[x][y] = []\n",
    "                    self.res[x][y].append(node.val)\n",
    "                        \n",
    "                    if node.left:\n",
    "                        q.append((node.left,(x-1,y-1)))\n",
    "                    if node.right:\n",
    "                        q.append((node.right,(x+1,y-1)))\n",
    "        bfs(root)\n",
    "        \n",
    "        self.res = [self.res[i] for i in sorted(self.res)]\n",
    "        ans = []\n",
    "        for d in self.res:\n",
    "            d_set = []\n",
    "           # print(d)\n",
    "            for m in d.values():\n",
    "                d_set += sorted(m)\n",
    "            ans.append(d_set)\n",
    "        return ans\n",
    "                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:\n",
    "        most_left_idx = 0\n",
    "        idx_node_d = collections.defaultdict(list)\n",
    "        queue = collections.deque([(root, 0)])\n",
    "\n",
    "        while queue:\n",
    "            new_elements = collections.defaultdict(list)\n",
    "            for i in range(len(queue)):                \n",
    "                node, x = queue.popleft()\n",
    "                most_left_idx = min(most_left_idx, x)\n",
    "                new_elements[x].append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append((node.left, x - 1))\n",
    "                if node.right:\n",
    "                    queue.append((node.right, x + 1))\n",
    "            for x, val in new_elements.items():\n",
    "                idx_node_d[x] += sorted(val)\n",
    "        \n",
    "        ans = []\n",
    "        while most_left_idx in idx_node_d:\n",
    "            ans.append(idx_node_d[most_left_idx])\n",
    "            most_left_idx += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:\n",
    "        m = {}\n",
    "\n",
    "        def helper(r: TreeNode, x: int, deep: int):\n",
    "            if r:\n",
    "                m[x] = m.get(x, []) + [(deep, r.val)]\n",
    "                helper(r.left, x - 1, deep + 1)\n",
    "                helper(r.right, x + 1, deep + 1)\n",
    "\n",
    "        helper(root, 0, 0)\n",
    "        res = []\n",
    "        for i in sorted(m.keys()):\n",
    "            res.append([mi[1] for mi in sorted(m[i])])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:\n",
    "        seen = collections.defaultdict(\n",
    "                  lambda: collections.defaultdict(list))\n",
    "        def helper(x,y,node):\n",
    "            if node:\n",
    "                seen[x][y].append(node)\n",
    "                helper(x-1,y+1,node.left)\n",
    "                helper(x+1,y+1,node.right)\n",
    "        helper(0,0,root)\n",
    "        ans = []\n",
    "        for i in sorted(seen):\n",
    "            temp = []\n",
    "            for j in sorted(seen[i]):\n",
    "                temp.extend(sorted(node.val for node in seen[i][j]))\n",
    "            ans.append(temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:\n",
    "        # null root?\n",
    "        # d = {x: [(-y, v), (-y, v)]}\n",
    "        d = collections.defaultdict(list)\n",
    "        def dfs(node, x, y):\n",
    "            if not node:\n",
    "                return\n",
    "            d[x].append([-y, node.val])\n",
    "            dfs(node.left, x - 1, y - 1)\n",
    "            dfs(node.right, x + 1, y - 1)\n",
    "        dfs(root, 0, 0)\n",
    "        result = []\n",
    "        for x in sorted(d.keys()):\n",
    "            ys_vals = d[x]\n",
    "            ys_vals.sort()\n",
    "            result.append([v for _, v in ys_vals ])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:\r\n",
    "        res = [[] for _ in range(2000)]\r\n",
    "        def helper(root, cur, level):\r\n",
    "            if not root: return\r\n",
    "            res[cur].append((level, root.val))\r\n",
    "            helper(root.left, cur - 1, level + 1)\r\n",
    "            helper(root.right, cur + 1, level + 1)\r\n",
    "        helper(root, 1000, 1)\r\n",
    "        memo = []\r\n",
    "        for i in res:\r\n",
    "            if not i: continue\r\n",
    "            i.sort()\r\n",
    "            memo.append([j for k, j in i])\r\n",
    "        return memo\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        m = defaultdict(list)\n",
    "        dq = deque()\n",
    "        dq.append([root, 0, 0])\n",
    "\n",
    "        while dq:\n",
    "            size = len(dq)\n",
    "            tmp = defaultdict(list)\n",
    "            while size:\n",
    "                o, x, y = dq.popleft()\n",
    "                tmp[y].append(o.val)\n",
    "                if o.left:\n",
    "                    dq.append([o.left, x + 1, y - 1])\n",
    "                if o.right:\n",
    "                    dq.append([o.right, x + 1, y + 1])\n",
    "                size -= 1\n",
    "            for k,v in tmp.items():\n",
    "                m[k].extend(sorted(v))\n",
    "        keys = sorted(m.keys())\n",
    "        ans = []\n",
    "        for k in keys:\n",
    "            ans.append(m[k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        stack = deque([( 0, root)])\n",
    "\n",
    "        while stack:\n",
    "\n",
    "            tmp = defaultdict(list)\n",
    "            for i in range(len(stack)):\n",
    "\n",
    "                c, node = stack.popleft()\n",
    "                tmp[c].append(node.val)\n",
    "                \n",
    "                if node.left:\n",
    "                    stack.append((c-1, node.left))\n",
    "                if node.right:\n",
    "                    stack.append((c+1, node.right))\n",
    "            for k, v in tmp.items():\n",
    "                dic[k].extend(sorted(v))\n",
    "        \n",
    "        ret = []\n",
    "        for k in sorted(dic.keys()):\n",
    "            ret.append(dic[k])\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        # 暴力法：从根节点开始遍历，记录val以及坐标，再排序\n",
    "        self.res = []\n",
    "\n",
    "        def dfs(node, i, j):\n",
    "            if not node:\n",
    "                return\n",
    "            self.res.append((node.val, i, j))\n",
    "            dfs(node.left, i + 1, j - 1)\n",
    "            dfs(node.right, i + 1, j + 1)\n",
    "        # main\n",
    "        dfs(root, 0, 0)\n",
    "        self.res.sort(key = lambda x: (x[2], x[1], x[0]))\n",
    "        self.ans = []\n",
    "        used = set()\n",
    "        for elem in self.res:\n",
    "            if elem[-1] not in used:\n",
    "                used.add(elem[-1])\n",
    "                self.ans.append([elem[0]])\n",
    "            else:\n",
    "                tmp = self.ans.pop(-1)\n",
    "                tmp.append(elem[0])\n",
    "                self.ans.append(tmp)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        # 4.25  14.32-14.46（自己能想到的思路，dfs将位置存储为哈希表键，节点值存为哈希表值，如果值多于一个存为列表，\n",
    "        # 然后对哈希表按键排序），不能解决排序问题\n",
    "        # 题解\n",
    "        # 15.05-\n",
    "        # 思路依然是哈希表+排序，只不过哈希键位Node,值位（col,row, val）三元组，\n",
    "        # dfs存储哈希表，最后对值进行排序，就会按照先列，后行，如果位置相同，值从小到大的顺序排序\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        hp = {root: (0, 0, root.val)}\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            col, row, val = hp[root]\n",
    "            if root.left:\n",
    "                hp[root.left] = (col-1, row+1, root.left.val)\n",
    "                dfs(root.left)\n",
    "            if root.right:\n",
    "                hp[root.right] = (col+1, row+1, root.right.val)\n",
    "                dfs(root.right)\n",
    "        dfs(root)\n",
    "        table = sorted(hp.values())\n",
    "        n = len(table)\n",
    "        i = 0\n",
    "        res = []\n",
    "        while i < n:\n",
    "            j = i+1\n",
    "            tmp = [table[i][2]]\n",
    "            while j<n and table[j][0] == table[j-1][0]:\n",
    "                tmp.append(table[j][2])\n",
    "                j+=1\n",
    "            res.append(tmp)\n",
    "            i = j\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def dfs(root, row, col):\n",
    "            if root:\n",
    "                res[col].add((row, root.val))\n",
    "                dfs(root.left, row + 1, col - 1)\n",
    "                dfs(root.right, row + 1, col + 1)\n",
    "\n",
    "        res = defaultdict(SortedList)\n",
    "        dfs(root, 0, 0)\n",
    "        return [[j[1] for j in res[i]] for i in sorted(res.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def dfs(root, row, col):\n",
    "            if root:\n",
    "                res.add((col, row, root.val))\n",
    "                dfs(root.left, row + 1, col - 1)\n",
    "                dfs(root.right, row + 1, col + 1)\n",
    "\n",
    "        res = SortedList()\n",
    "        dfs(root, 0, 0)\n",
    "        # print(res)\n",
    "        f = res[0][0]\n",
    "        ans, tmp = [], []\n",
    "        for c, _, i in res:\n",
    "            if c == f:\n",
    "                tmp.append(i)\n",
    "            else:\n",
    "                ans.append(tmp)\n",
    "                tmp = [i]\n",
    "            f = c\n",
    "        if tmp:\n",
    "            ans.append(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        node_positions=defaultdict(list)\n",
    "\n",
    "        def dfs(node,row,col):\n",
    "            if not node:\n",
    "                return\n",
    "            node_positions[col].append((row,node.val))\n",
    "            dfs(node.left,row+2,col-1)\n",
    "            dfs(node.right,row+1,col+1)\n",
    "        dfs(root,0,0)\n",
    "        result=[]\n",
    "        sorted_cols=sorted(node_positions.keys())\n",
    "        for col in sorted_cols:\n",
    "            nodes=sorted(node_positions[col])\n",
    "            result.append([val for row,val in nodes])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        self.l_vals = {}\n",
    "        self.travel(root, 0, 0)\n",
    "        vals = []\n",
    "        for key in sorted(list(map(int, self.l_vals.keys()))):\n",
    "            tmp = []\n",
    "            for i in sorted(list(map(int, self.l_vals[str(key)].keys()))):\n",
    "                tmp.extend(self.l_vals[str(key)][str(i)])\n",
    "            vals.append(tmp)\n",
    "        return vals\n",
    "\n",
    "    def travel(self, root, p, level):\n",
    "        def insert(array, val):\n",
    "            for i in range(len(array)):\n",
    "                if array[i] <= val:\n",
    "                    continue\n",
    "                else:\n",
    "                    l = array[:i]\n",
    "                    l.append(val)\n",
    "                    l.extend(array[i:])\n",
    "                    return l\n",
    "            array.append(val)\n",
    "            return array\n",
    "\n",
    "        if not root:\n",
    "            return\n",
    "        self.travel(root.left, p - 1, level + 1)\n",
    "        self.travel(root.right, p + 1, level + 1)\n",
    "        if str(p) not in self.l_vals.keys():\n",
    "            self.l_vals[str(p)] = {str(level): [root.val]}\n",
    "        else:\n",
    "            if str(level) not in self.l_vals[str(p)].keys():\n",
    "                self.l_vals[str(p)][str(level)] = [root.val]\n",
    "            else:\n",
    "                self.l_vals[str(p)][str(level)] = insert(self.l_vals[str(p)][str(level)], root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# dfs + 排序\n",
    "# O(nlogn) O(n)\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        # hashmap stores mapping from col to (row, node value)\n",
    "        hashmap = collections.defaultdict(list)\n",
    "        def dfs(node,i,j):\n",
    "            if not node:\n",
    "                return\n",
    "            hashmap[j].append((i,node.val))\n",
    "            dfs(node.left,i+1,j-1)\n",
    "            dfs(node.right,i+1,j+1)\n",
    "        dfs(root,0,0)\n",
    "        \n",
    "        print(hashmap)\n",
    "        res = []\n",
    "        for j in sorted(hashmap.keys()):\n",
    "            tmp = []\n",
    "            for i,val in sorted(hashmap[j]):\n",
    "                tmp.append(val)\n",
    "            res.append(tmp)\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
